#include <iostream>
using namespace std;

class DNode {
public:
  int value;
  DNode *prev;
  DNode *next;

  DNode(int v, DNode *p, DNode *n): value(v), prev(p), next(n) {
    cout << "A DNode with value: " << v << "was created." << endl;
  }
};

class DoubleLinkList {
public:
  DNode *head;
  DNode *tail;
  int size;

  // Constructor
  // DoubleLinkList dll; 
  DoubleLinkList() {
    size = 0;
    head = nullptr;
    tail = nullptr;

    cout << "An empty DoubleLinkList is created." << endl;
  }

  void addAtIndex(int pos, int val) {
    // 1. 如果 pos 的位置不合法，就直接返回
    if (pos < 0 || pos > size) {
      return;
    }

    ++size;
    DNode *toAdd = new DNode(val, nullptr, nullptr);

    if (head == nullptr) { // tail == nullptr
      // 2. 如果调用 addAtIndex 的时候，是一个空的双向链表
      head = toAdd;
      tail = toAdd;
    }
    else {
      // 3. 调用 addAtIndex 的时候，链表已经不为空了
      // pos = 2
      //                           tmp
      //             0      1      2      3
      // nullptr <- 11 <-> 12 <-> 13 <-> 14 -> nullptr
      DNode *tmp = head;
      int counter = 0;
      while (counter < pos) {
        tmp = tmp->next;
        ++counter;
      }

      // tmp 指向的就是插入的位置
      // 只在插入位置不等于表头或表尾的时候
      // pos = 0
      if (pos == 0) {
        // 表头插入
        toAdd->next = head;
        head->prev = toAdd;
        head = toAdd;
      }
      else if (pos == size - 1) {
        // 表尾插入
        toAdd->prev = tail;
        tail->next = toAdd;
        tail = toAdd;
      }
      else {
        toAdd->prev = tmp->prev;
        tmp->prev->next = toAdd;
        toAdd->next = tmp;
        tmp->prev = toAdd;
      }
    }
  }

  void addAtTail(int val) {
    addAtIndex(size, val);
  }

  // 正向打印
  void print() {
    if (head == nullptr) {
      cout << "An empty double link list." << endl;
      return;
    }

    DNode *p = head;

    while (p != nullptr) {
      cout << p->value << " ";
      p = p->next;
    }

    cout << endl;
    return;
  }

  // 逆向打印
  void printReverse() {
    if (tail == nullptr) {
      cout << "An empty double link list" << endl;
      return  ;
    }

    DNode *p = tail;
    while (p != nullptr) {
      cout << p->value << " ";
      p = p->prev;
    }
    cout << endl;
    return;
  }

  // 删除 pos 位置的节点
  /**
   1. 删除位置不合法
   2. 删除表头位置的节点 => 更新 head
   3. 删除表尾的节点 => 更新 tail
   4. 删除链表中间位置的节点
  */
  void deleteAtIdx(int pos) {
    if (pos < 0 || pos >= size) {
      cout << "Invalid deletion position: " << pos << endl;
      return;
    }

    if (pos == 0) {
      // 删除表头位置的节点
      DNode *p = head->next;
      head->next = nullptr;

      if (p != nullptr) {
        p->prev = nullptr;  
      }
      
      delete head;

      head = p;
      --size;

      if (size == 0) {
        tail = nullptr;
      }
    }
    else if (pos == size - 1) {
      // 删除链表尾部的节点
      DNode *p = tail->prev;

      if (p != nullptr) {
        p->next = nullptr;
      }
      
      tail->prev = nullptr;

      delete tail;

      tail = p;
      --size;

      if (size == 0) {
        head = nullptr;
      }
    }
    else {
      // 删除中间节点的情况
      // 1. 找到位置 pos 的节点
      DNode *p = head;
      int i = 0;
      while (i < pos) {
        p = p->next;
        ++i;
      }

      p->prev->next = p->next;
      p->next->prev = p->prev;

      p->prev = nullptr;
      p->next = nullptr;
      delete p;
      --size;
    }
  }
};
